#include <stdio.h>
#include <stdlib.h>
/*
void merge(int a[], int low, int mid, int high)
    把a[low]~a[mid]和a[mid+1]~a[high]两段有序的数组进行排序
    mid 是前半段数组最后一个 low=0 mid=0 high=1 是对a[2]进行排序
    a[0]~~a[0]
    a[0+1]~~a[1]
*/
void merge(int a[], int low, int mid, int high)
{
    int *b = (int *)malloc(sizeof(int) * (high + 1));
    int i, j, k;
    i = low;
    j = mid + 1;
    k = 0;
    while (i <= mid && j <= high)
    {
        while (i <= mid && j <= high && a[i] < a[j])
        {
            *(b + k++) = a[i++];
        }
        while (i <= mid && j <= high && a[i] > a[j])
        {
            *(b + k++) = a[j++];
        }
    }
    for (; i <= mid;)
        *(b + k++) = a[i++];
    for (; j <= high;)
        *(b + k++) = a[j++];

    for (int m = low; m <= high; m++)
    {
        a[m] = *(b + m - low);
    }
    free(b);
}
//递归 自顶向下
void m_s(int a[], int l, int r)
{
    /*
        类似树的后序遍历
        先排序左子树 再排序右子树 最后左右子树合并
    */
    if (r <= l)
        return;
    int m = (l + r) / 2; //把序列一分为二-->左右两个子序列
    m_s(a, l, m);        //对左子序列进行归并
    m_s(a, m + 1, r);    //对右子序列进行归并
    merge(a, l, m, r);   //左右子序列归并
}
void merge_sort(int a[], int n)
{
    m_s(a, 0, n - 1);
}
//自底向上非递归排序
void merge_sortBU(int a[], int n)
{
    int d;
    for (d = 2; d <= 2 * n; d *= 2)
    {
        for (int i = 0; i <= n; i += d)
        {
            //对于子串的划分！！！
            int r = (i + d - 1 < n - 1) ? i + d - 1 : n - 1;
            int m = (i + d - 1 < n - 1) ? (i + d - 1 + i) / 2 : i + d / 2 - 1;
            merge(a, i, m, r);
        }
        for (int k = 0; k < n; k++)
            printf("%3d", a[k]);
        printf("\n");
    }
}
int main()
{
    int a[] = {4, 3, 8, 2, 7, 11, 6, 1, 9, 0, 65, 32, 10, 15, 36, 12, 13};
    int n = 17;
    merge_sortBU(a, n);
    for (int i = 0; i < n; i++)
        printf("%3d", a[i]);
    getchar();
    return 0;
}
